
import java.math.BigInteger;
import java.awt.*;
import javax.swing.*;
import java.awt.event.*;
import java.io.*;
/*
* 创建大素数,按要求随机生成一个大数，用isProbablePrime（）使这个数极有可能是素数
* 再用1到int的最大值去除之测试，直到通过为止
* */
public  class LargePrime {
    //实现一个大素数生成算法
    public static BigInteger makePrime(int bits) {
        BigInteger start = bigRandom(bits);
        return nextPrime(start);
    }


    // 下面的 BigInteger.ZERO 和 BigInteger.ONE 在 JDK 1.1 中是无效的
    private static final BigInteger ZERO = BigInteger.ZERO;
    private static final BigInteger ONE = BigInteger.ONE;
    private static final BigInteger TWO = new BigInteger("2");

    // 产生一个错误素数的概率小于 1/2 的 ERR_VAL 次方，可以将 ERR_VAL 定义为 200，降低其错误率
    // Java 应该使用的是 Miller-Rabin 测试法，这种错误概率基本上可以认为是无错误。
    private static final int ERR_VAL = 100;
    private static StringBuffer[] digits = {new StringBuffer("0"), new StringBuffer("1"), new StringBuffer("2"), new StringBuffer("3"), new StringBuffer("4"), new StringBuffer("5"),
            new StringBuffer("6"), new StringBuffer("7"), new StringBuffer("8"), new StringBuffer("9")};

    private static StringBuffer randomDigit(boolean isZeroOK) {
        // 产生一个随机的数字（字符串形式的），isZeroOK 决定这个数字是否可以为 0
        int index;
        if (isZeroOK)
            index = (int) Math.floor(Math.random() * 10);
        else
            index = 1 + (int) Math.floor(Math.random() * 9);
        return (digits[index]);
    }
    /**
     * 产生一个二进制下为bits位的随机大整数，各位上的数字都是随机产生的，首位不为 0
     * bits：二进制位数
     * */
    public static BigInteger bigRandom(int bits) {
        BigInteger result = new BigInteger("1");
        for(int i=0;i<bits-2;++i){
            result=result.shiftLeft(1);

            if((int)(Math.random()*10)<5)
                result=result.add(ONE);

        }
        return bits==1? result:result.shiftLeft(1).add(ONE);
    }

    private static boolean isEven(BigInteger n) {
        // 测试一个大整数是否为偶数
        return (n.mod(TWO).equals(ZERO));
    }

    public static BigInteger nextPrime(BigInteger start) {
        // 产生一个比给定大整数 start 大的素数，错误率低于 1/2 的 ERR_VAL 次方
        if (isEven(start))
            start = start.add(ONE);
        else
            start = start.add(TWO);
        if (start.isProbablePrime(ERR_VAL))
            return (start);
        else
            // 采用递归方式（递归的层数会是个天文数字吗？）
            return (nextPrime(start));
    }

    //判断素数////////////////////////////////////////////////////////////////////////////////////
    public static boolean isPrime(double n) {
        //如果n大于2 继续判断 否则 isPrime的值不变 2素数
        if (n > 2) {
            //如果n是大于2的偶数 认定不是素数 修改变量值为false
            if (n % 2 == 0) {
                return false;
            } else {
                //循环判断如果找到一个可以整除的数 则判定不是素数跳出循环 因为是判断奇数 因此 2 4 6 ...?
                //不用考虑 循环递增2 即?3 5 7 ...
                for (int i = 3; i <= (int) Math.sqrt(n); i += 2) {
                    if (n % i == 0) {
                        return false;
                    }
                }
            }

        }
        return true;

    }
    static BigInteger LONGMAX=new BigInteger(""+Long.MAX_VALUE);
    public static boolean isPrime(BigInteger n) {
        if (n.compareTo(LONGMAX)==-1) return isPrime(n.doubleValue());
        //如果n大于2 继续判断 否则 isPrime的值不变 2素数
        if (n.compareTo(TWO)==1) {
            //如果n是大于2的偶数 认定不是素数 修改变量值为false
            if (n.and(ONE).equals(ZERO)) {
                return false;
            } else {
                //循环判断如果找到一个可以整除的数 则判定不是素数跳出循环 因为是判断奇数 因此 2 4 6 ...?
                //不用考虑 循环递增2 即?3 5 7 ...

                for (long i = 3; i <= Long.MAX_VALUE; i += 2) {
                    if (n.mod(new BigInteger(""+i)).equals(ZERO)) {
                        return false;
                    }
                }
                if(LONGMAX.subtract(LONGMAX).compareTo(n)==1) return true;
                else for (BigInteger i = LONGMAX; i.compareTo(n)==-1 ; i =i.add(TWO)) {
                    if (n.mod(i).equals(ZERO)) {
                        return false;
                    }
                }
            }

        }
        return true;

    }
    public static boolean isProbablePrime(BigInteger n,BigInteger MAX) {
//        if (n.compareTo(LONGMAX)==-1) return isPrime(n.doubleValue());
        //如果n大于2 继续判断 否则 isPrime的值不变 2素数
        if (n.compareTo(TWO)==1) {
            //如果n是大于2的偶数 认定不是素数 修改变量值为false
            if (n.and(ONE).equals(ZERO)) {
                return false;
            } else {
                //循环判断如果找到一个可以整除的数 则判定不是素数跳出循环 因为是判断奇数 因此 2 4 6 ...?
                //不用考虑 循环递增2 即?3 5 7 ...

                for (BigInteger i = new BigInteger("3"); i.compareTo(MAX)==-1 ; i =i.add(TWO)) {
                    if (n.mod(i).equals(ZERO)) {
                        return false;
                    }
                }
            }

        }
        return true;

    }
}